
# -*- coding:utf-8 -*-

from base.ListNode import ListNode

"""
 leetcode #92 反转链表 II

 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

 说明:
 1 ≤ m ≤ n ≤ 链表长度。

 示例:

 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 输出: 1->4->3->2->5->NULL

 思路：分两步：
 1. 将链表从位置m和n断开，分成三段：
 M段：root ~ mtail
 R段：rhead ~ rtail
 N段：nhead ~ 结尾

 2. 将 R 段进行反转
 3. 最后R头尾和M段 N段拼接即可

 """
class ReverseLinkedList2:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if m == n:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        mtail = dummy
        nhead = dummy
        while n > 0:
            n -= 1
            nhead = nhead.next
            
        rtail = nhead
        nhead = nhead.next
        rtail.next = None

        while m > 1:
            m -= 1
            mtail = mtail.next
        rhead = mtail.next
        mtail.next = None

        root = ListNode(-1)
        root.next = nhead
        next:ListNode = None
        while rhead:
            next = rhead.next
            rhead.next = root.next

            root.next = rhead
            rhead = next

        mtail.next = root.next
        return dummy.next
        